---
title: "L2-014 列车调度"
created: 2025-11-28
tags:
  - 算法
---

# L2-014 列车调度

## 题目 [L2-014 列车调度](https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId=994805063166312448&page=1)

![[image-b2d8dffb.png]]

## 思路分析

![[image-ba8390d0.png]]

是拦截导弹的简化

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
int stackTop[N],cnt;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,x;cin>>n;

	while(n--){
		cin>>x;

		int l=0,r=cnt;
		while(l<r){ //----- |-----
			int mid=l+r>>1;
			if(stackTop[mid]>=x)
				r=mid;
			else
				l=mid+1;
		}
		if(stackTop[r]<x)	r++;
		cnt=max(cnt,r);
		stackTop[r]=x;
	}
	cout<<cnt;
	return 0;
}
```

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;

const int N=1e5+10;
set<int> stackTop;

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,x;cin>>n;

	while(n--){
		cin>>x;

		auto i = stackTop.lower_bound(x);
		if(i!=stackTop.end()){
			stackTop.erase(i);
			stackTop.insert(x);
		}else{
			stackTop.insert(x);
		}
	}
	cout<<stackTop.size();
	return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[L2-013 红色警报|L2-013 红色警报]] 🏠 [[00-天梯赛]] ➡️ [[L2-015 互评成绩|L2-015 互评成绩]]